package leecode.二叉树.遍历;

/**
 * @author wangxi created on 2023/4/22 22:52
 * @version v1.0
 * https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 * 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
 * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。
 * 下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
 */
public class InOrderGetNextNode {
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }


    // 参考：https://cloud.tencent.com/developer/article/1850940
    // 注意：题目没有给出root节点，因此可以根据 pNode.next != null 一直找可以找到root节点
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        }
        if (pNode.right != null) {
            // 如果当前节点有右儿子，下一节点为当前节点「右子树中最靠左的节点」
            // 此种情况是 pNode有可能是作为左节点，或者为右节点
            TreeLinkNode node = pNode.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        } else {
            // 如果当前节点没有右儿子，则「往上找父节点」，直到出现满足「其左儿子是当前节点」的父节点
            // 此种情况是 pNode有可能是作为左节点，或者为右节点
            // 注意：pNode有可能是root节点
            while (pNode.next != null && pNode.next.left != pNode) {
                pNode = pNode.next;
            }
            return pNode.next;
        }
    }
}
